In recent years, attention has been attracted to a Low-Density Parity-Check (LDPC) code as an error correction code that provides high error correction capability with a feasible circuit scale. Due to its high error correction capability and ease of implementation, an LDPC code has been adopted in an error correction code for IEEE802.11n high-speed radio LAN (Local Area Network) systems, digital broadcasting systems, and so forth.
An LDPC code is an error correction code defined by a low-density parity check matrix (that is, a parity check matrix in which there are far fewer 1 elements than 0 elements). An LDPC code is a block code having a block length equal to number of columns N of a parity check matrix.
However, a characteristic of many current communication systems is that communication is based on variable-length packets and frames, as in the case of the Ethernet (registered trademark). A problem with applying an LDPC code, which is a block code, to a system of this kind is, for example, how to make a fixed-length LDPC code block correspond to a variable-length Ethernet (registered trademark) frame. With IEEE802.11n, a wireless LAN standard for which an LDPC code has been adopted, adjustment of the length of a transmission information sequence and an LDPC code block length is performed by applying padding and/or puncturing to a transmission information sequence. However, a problem with this is the necessity of changing the coding rate by means of padding or puncturing, and of performing redundant sequence transmission.
In contrast to this kind of block-wise LDPC code (hereinafter referred to as “LDPC-BC: Low-Density Parity-Check Block Code”), an LDPC-CC allowing encoding and decoding of information sequences with arbitrary length has been investigated (see Non-Patent Document 1).
An LDPC-CC is a convolutional code defined by a low-density parity-check matrix.
FIG. 1 shows, as an example, parity check matrix H[0,n]T of an LDPC-CC for which coding rate R=½ (=b/c).
With an LDPC-CC, elements h1(m)(t) and h2(m)(t) of parity check matrix H[0,n]T are 0 or 1. Also, all elements other than h1(m)(t) and h2(m)(t) included in parity check matrix H[0,n]T are 0. In FIG. 1, M represents the memory length for an LDPC-CC, and n represents the length of a transmission information sequence. As shown in FIG. 1, a characteristic of a parity check matrix of an LDPC-CC is that it is a parallelogram-shaped matrix in which 1 is placed only in diagonal terms of the matrix and neighboring elements, and the bottom-left and top-right elements of the matrix are zero.
Here, if an example in which coding rate R=½ (=b/c) is shown, when h1(0)(t)=1 and h2(0)(t)=1, LDPC-CC encoding is performed by means of Equation (1) and Equation (2) in accordance with parity check matrix H[0,n]T in FIG. 1.
                    (                  Equation          ⁢                                          ⁢          1                )                                                                      v                      1            ,            t                          =                  u          t                                    [        1        ]                                (                  Equation          ⁢                                          ⁢          2                )                                                                      v                      2            ,            t                          =                                            ∑                              i                =                0                            M                        ⁢                                                            h                  1                                      (                    i                    )                                                  ⁡                                  (                  t                  )                                            ⁢                              u                                  t                  -                  i                                                              +                                    ∑                              i                =                1                            M                        ⁢                                                            h                  2                                      (                    i                    )                                                  ⁡                                  (                  t                  )                                            ⁢                              v                                  2                  ,                                      t                    -                    i                                                                                                          [        2        ]            
Here, ut represents a transmission information sequence, and v1,t and v2,t represent transmission codeword sequences.
FIG. 2 shows an example of a main configuration of an LDPC-CC encoder that executes Equation (1) and Equation (2). As shown in FIG. 2, LDPC-CC encoder 10 comprises shift registers 11-1 through 11-M and 14-1 through 14-M, weight multipliers 12-0 through 12-M and 13-0 through 13-M, modulo 2 adder (exclusive OR computing element) 15, bit counter 16, and weight control section 17.
Shift registers 11-1 through 11-M and 14-1 through 14-M are registers storing and v1,t-i and v2,t-i (where i=0, . . . , M) respectively, and at a timing at which the next input comes in, send a stored value to the adjacent shift register to the right, and store a new value sent from the adjacent shift register to the left.
Weight multipliers 12-0 through 12-M and 13-0 through 13-M switch a weight value to 0 or 1 in accordance with a control signal output from weight control section 17. Based on a count output from bit counter 16 and a weight pattern conforming to a parity check matrix stored in weight control section 17, weight control section 17 sends the values of h1(m)(t) and h2(m)(t) at that timing to weight multipliers 12-0 through 12-M and 13-0 through 13-M. Modulo 2 adder 15 performs modulo 2 addition on the outputs of weight multipliers 12-0 through 12-M and 13-0 through 13-M, and calculates v2,t. Bit counter 16 counts the number of bits of an input transmission information sequence.
By employing this kind of configuration, LDPC-CC encoder 10 can perform LDPC-CC encoding in accordance with a parity check matrix.
A characteristic of an LDPC-CC encoder is that it can be implemented with extremely simple circuitry as compared with the circuitry of an encoder that performs generator matrix multiplication, or an LDPC-BC encoder that performs computation based on backward substitution or forward substitution. Also, since an LDPC-CC is a convolutional code, it is not necessary to divide a transmission information sequence into fixed-length blocks when encoding, and an information sequence of any length can be encoded.
In LDPC-CC decoding, a sum-product algorithm can be applied based on a parity check matrix in the same way as with an LDPC-BC. Therefore, it is not necessary to use a BCJR (Bahl, Cocke, Jeinek, Raviv) algorithm, or a decoding algorithm based on maximum likelihood sequence estimation such as a Viterbi algorithm, and decoding processing can be completed with little processing delay. Furthermore, in Non-Patent Document 1, a pipeline-based decoding algorithm is proposed that takes advantage of the structure of the parity check matrix, in which 1s are arranged in a parallelogram configuration.
When LDPC-CC and LDPC-BC decoding characteristics are compared using parameters such that the decoder circuit scales are equivalent, LDPC-CC decoding characteristics are shown to be superior (see Non-Patent Document 1).
Now we consider that a encoder terminate LDPC-CC encoding at an arbitrary length n, and a decoder decodes a corresponding received codeword sequence. In this case, the decoder requires the codeword that encoded transmission information sequences after n-th bit and shift register states at the end of encoding in order to make probability propagation of the rear 2M bits equivalent to that of the other bits in sum-product decoding.
However, when a transmission information sequence is simply encoded, since encoder shift register states at the end of encoding depend on the transmission information sequence, it is difficult to decide those states uniquely at a receiver side.
If decoding processing is performed on the receiver side based on a received codeword sequence in such a situation, a phenomenon occurs whereby errors increase at the end of a received information sequence obtained after decoding, particularly in the rear 2M bits.
In order to prevent such errors, it is necessary for terminating processing (termination) that uniquely decides a terminal state of encoding to be executed on a transmission information sequence.
With a convolutional code conforming to IEEE802.11n, termination is executed by adding “tail bits” comprising the six 0s to the rear of a transmission information sequence when performing encoding. The length of tail bits, six, is the same number as shift registers in an encoder. By so doing, the state of an encoder shift registers can be made all-zeros at a point in time at which tail bit input ends. A codeword output when a tail bit is input is necessary for decoding processing on the receiver side, and is therefore transmitted to the receiver side together with a transmission codeword.
In the case of an LDPC-CC, as shown in Equation (1), codewords v2,t-i for the past M times are necessary to find codeword v2,t, and therefore shift registers for storing codeword v2,t−i for the past M times are provided in an LDPC-CC encoder. A register storing a transmission information sequence can be set to an all-zero state by making the end of a transmission information sequence a length-M all-zero sequence (termination), but a problem is that it is difficult to set a shift register storing codeword v2,t-i to an all-zero state with only this termination processing.
In Non-Patent Document 2, termination processing is proposed that sets the state of a shift register at the end of encoding to all-zeros by performing encoding after adding a termination sequence to the rear of a transmission information sequence.
In the termination processing proposed in Non-Patent Document 2, a transmission codeword sequence is defined as shown in Equation (3).
Equation (3) is an example for a case in which coding rate R=½. In Equation (3), v1×2 is a length-2n codeword sequence obtained by convolutional encoding of a length-n information sequence, x1×2L is a termination codeword sequence obtained by convolutional encoding of a length-L termination sequence, and 01×2M is a length-2M 0-sequence.
[3][v1×2n,x1×2L,01×2M]H′2(n+L+M)×(n+L+M)=01×(n+L+M) . . .   (Equation 3)
Here, termination sequence x1×2L is decided by Equation (4) and Equation (5).
                    (                  Equation          ⁢                                          ⁢          4                )                                                                                  [                                          v                                  1                  ×                  2                  ⁢                  n                                            ,                              x                                  1                  ×                  2                  ⁢                  L                                            ,                              0                                  1                  ×                  2                  ⁢                  M                                                      ]                    ⁡                      [                                                                                A                                          2                      ⁢                      n                      ×                      n                                                                                                            B                                          2                      ⁢                      n                      ×                                              (                                                  L                          +                          M                                                )                                                                                                                                                              0                                          2                      ⁢                      L                      ×                      n                                                                                                            D                                          2                      ⁢                      L                      ×                                              (                                                  L                          +                          M                                                )                                                                                                                                                              0                                          2                      ⁢                      M                      ×                      n                                                                                                            F                                          2                      ⁢                      M                      ×                                              (                                                  L                          +                          M                                                )                                                                                                                  ]                          =                  0                      1            ×                          (                              n                +                L                +                M                            )                                                          [        4        ]                                (                  Equation          ⁢                                          ⁢          5                )                                                                                  x                          1              ×              2              ⁢              L                                ⁢                      D                          2              ⁢              L              ×                              (                                  L                  +                  M                                )                                                    =                                            v                              1                ×                2                ⁢                n                                      ⁢                          B                              2                ⁢                n                ×                                  (                                      L                    +                    M                                    )                                                              =          β                                    [        5        ]            
The state of a shift register can be set to an all-zero state by encoding a transmission codeword sequence to which such a termination sequence has been added with an LDPC-CC encoder. By having a transceiver-side communication apparatus transmit a transmission codeword that has undergone termination processing in this way to the receiver side, the receiver side decoder can uniquely decide a shift register state at the end of encoding, and performs error correction decoding at a desired level of performance.    Non-Patent Document 1: Alberto Jimenez Felstorom, and Kamil Sh. Zigangirov, “Time-Varying Periodic Convolutional Codes With Low-Density Parity-Check Matrix.”, IEEE Transactions on Information Theory, Vol. 45, No. 6, pp. 2181-2191, September, 1999.    Non-Patent Document 2: Zhengang Chen, Stephen Bates, and Ziaodai Dong, “Low-Density Parity-Cheek Convolutional Codes Applied to Packet Based Communication Systems”, Proceeding of IEEE Globecom 2005, pp. 1250-1254.    Non-Patent Document 3: Stephen Bates, Duncan G. Elliott, and Ramkrishna Swamy, “Termination Sequence Generation Circuits for Low-Density Parity-Check Convolutional Codes,” IEEE Transaction on Circuits and Systems-I: Regular Papers, vol. 53, no. 9, pp. 1909-1917, September 2006    Non-Patent Document 4: S. Lin, D. J. Jr., Costello, “Error control coding: Fundamentals and applications,”,582-598, Prentice-Hall.    Non-Patent Document 5: R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello Jr., “LDPC block and convolutional codes based on circulant matrices,” IEEE Trans. Inform. Theory, vol. 50, no. 12, pp. 2966-2984, December 2004.    Non-Patent Document 6: G. Richter, M. Kaupper, and K. Sh. Zigangirov, “Irregular low-density parity-Check convolutional codes based on protographs,” Proceeding of IEEE ISIT 2006, pp 1633-1637.    Non-Patent Document 7: A. Pusane, R. Smarandache, P. Vontobel, and D. J. Costello Jr., “On deriving good LDPC convolutional codes from QC LDPC block codes,” Proc. of IEEE ISIT 2007, pp. 1221-1225, June 2007.    Non-Patent Document 8: Howard H. MA and Jack K. Wolf, On “Tail Bitin Convolutional Codes”, IEEE Transactions on communications, vol. COM-34, No. 2, pp. 104-111, February 1986